//
// Created by francklinson on 2021/5/21.
//
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumSize(vector<int> &nums, int maxOperations) {//二分
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long long ops = 0;
            for (int x: nums) {
                ops += (x - 1) / y; // 把某个袋子中的球 分成每袋不超过y个的操作数
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            } else {
                left = y + 1;
            }
        }
        return ans;
    }
};


int main() {
    vector<int> v{2, 4, 8, 2};
    vector<int> v2{9};
    vector<int> v3{7, 17};
    vector<int> v4{431, 922, 158, 60, 192, 14, 788, 146, 788, 775, 772, 792, 68, 143, 376, 375, 877, 516, 595, 82, 56,
                   704, 160, 403, 713, 504, 67, 332, 26};
    Solution sol;
    cout << sol.minimumSize(v, 4) << endl;
    cout << sol.minimumSize(v2, 2) << endl;
    cout << sol.minimumSize(v3, 2) << endl;
    cout << sol.minimumSize(v4, 80) << endl;
    return 0;
}